package 二叉树遍历;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Stack;

/**
 * 二叉树遍历
 * <p>
 * 前序：根左右
 * 中序：左根右
 * 后序：左右根
 * 层序：从上到下，从左到右
 */
public class Solution {
    public static void main(String[] args) {
        TreeNode node11 = new TreeNode(11, null, null);
        TreeNode node10 = new TreeNode(10, null, null);
        TreeNode node3 = new TreeNode(3, null, null);
        TreeNode node5 = new TreeNode(5, node10, node11);
        TreeNode node4 = new TreeNode(4, null, null);
        TreeNode node2 = new TreeNode(2, node4, node5);
        TreeNode node1 = new TreeNode(1, node2, node3);


        System.out.print("递归法：");
        recursion(node1);
        System.out.println();

        System.out.print("序遍历迭代法：");
        List list = new ArrayList();
        levelTraverse(node1, 1, list);
        System.out.println("list = " + list);

        System.out.print("前序遍历迭代法：");
        prevIterate(node1);
        System.out.println();

        System.out.print("中序遍历迭代法：");
        midIterate(node1);
        System.out.println();

        System.out.print("后序遍历迭代法：");
        postIterate(node1);
        System.out.println();

        System.out.print("层序遍历迭代法：");
        leveIterate(node1);
        System.out.println();

        System.out.print("前序遍历morris法：");
        prevMorris(node1);
        System.out.println();

        System.out.print("中序遍历morris法：");
        midMorris(node1);
        System.out.println();

        System.out.print("后序遍历morris法：");
        postMorris(node1);
        System.out.println();
    }


    /**
     * 前序递归遍历
     */
    public static void recursion(TreeNode root) {
        if (null == root) {
            return;
        }

        recursion(root.left);

        System.out.print(root.v + " ");

        recursion(root.right);

    }

    /**
     * 层级递归遍历
     */
    public static void levelTraverse(TreeNode root, int i, List list) {
        if (null == root) {
            return;
        }

        int size = list.size();
        if (size <= i) {
            for (int j = 0; j <= i - size; j++) {
                list.add(size + j, null);
            }
        }
        list.set(i, root.v);

        levelTraverse(root.left, 2 * i, list);

        levelTraverse(root.right, 2 * i + 1, list);

    }

    /**
     * 前序迭代法遍历
     */
    public static void prevIterate(TreeNode root) {
        if (null == root) {
            return;
        }

        Stack<TreeNode> stack = new Stack<>();

        stack.push(root);

        while (!stack.isEmpty()) {
            TreeNode pop = stack.pop();
            System.out.print(pop.v + " ");

            if (null != pop.right) {
                stack.push(pop.right);
            }
            if (null != pop.left) {
                stack.push(pop.left);
            }
        }
    }

    /**
     * 中序迭代法遍历
     */
    public static void midIterate(TreeNode root) {
        if (null == root) {
            return;
        }

        Stack<TreeNode> stack = new Stack<>();
        while (!stack.isEmpty() || root != null) {
            if (root != null) {
                stack.push(root);
                root = root.left;
            } else {
                root = stack.pop();
                System.out.print(root.v + " ");
                root = root.right;
            }
        }
    }

    /**
     * 后序迭代法遍历
     */
    public static void postIterate(TreeNode root) {
        if (null == root) {
            return;
        }

        Stack<TreeNode> stack = new Stack<>();
        TreeNode prev = null;
        while (!stack.isEmpty() || root != null) {
            // 最左边的节点最先push进去
            while (root != null) {
                stack.push(root);
                root = root.left;
            }

            root = stack.pop();
            if (root.right == null || root.right == prev) {
                // 没有右节点，可以打印了
                System.out.print(root.v + " ");
                prev = root;
                root = null;
            } else {
                // 有右节点，将当前节点push，下次循环将right节点push进去
                stack.push(root);
                root = root.right;
            }
        }
    }

    /**
     * 层序迭代法遍历
     */
    public static void leveIterate(TreeNode root) {
        if (null == root) {
            return;
        }

        LinkedList<TreeNode> queue = new LinkedList<>();

        queue.offer(root);

        while (!queue.isEmpty()) {
            root = queue.poll();
            System.out.print(root.v + " ");

            if (root.left != null) {
                queue.offer(root.left);
            }
            if (root.right != null) {
                queue.offer(root.right);
            }
        }
    }


    /**
     * morris前序遍历  线索二叉树
     */
    public static void prevMorris(TreeNode cur) {

        if (null == cur) {
            return;
        }

        TreeNode mostRight;
        while (cur != null) {
            // 找当前节点的，前驱节点，给前驱节点添加线索指针
            mostRight = cur.left;
            if (mostRight != null) {  // 到达最左边节点

                while (mostRight.right != null && mostRight.right != cur) {
                    mostRight = mostRight.right;
                }

                if (mostRight.right == null) {
                    // 开到前驱节点，建立线索指针
                    mostRight.right = cur;
                    System.out.print(cur.v + " ");
                    cur = cur.left;
                    continue;
                } else {
                    // 删除线索指针
                    mostRight.right = null;
                }

            } else {
                System.out.print(cur.v + " ");
            }
            cur = cur.right;
        }


    }

    /**
     * morris中序遍历
     */
    public static void midMorris(TreeNode cur) {

        if (null == cur) {
            return;
        }

        TreeNode mostRight;
        while (cur != null) {
            // 找当前节点的，前驱节点，给前驱节点添加线索指针
            mostRight = cur.left;
            if (mostRight != null) {  // 到达最左边节点

                while (mostRight.right != null && mostRight.right != cur) {
                    mostRight = mostRight.right;
                }

                if (mostRight.right == null) {
                    // 开到前驱节点，建立线索指针
                    mostRight.right = cur;
                    //System.out.print(cur.v + " ");
                    cur = cur.left;
                    continue;
                } else {
                    // 删除线索指针
                    mostRight.right = null;
                }

            } else {
                //System.out.print(cur.v + " ");
            }
            System.out.print(cur.v + " ");
            cur = cur.right;
        }
    }

    /**
     * morris后序遍历
     */
    public static void postMorris(TreeNode root) {

        TreeNode cur = root;

        if (null == cur) {
            return;
        }

        TreeNode mostRight;
        while (cur != null) {
            // 找当前节点的，前驱节点，给前驱节点添加线索指针
            mostRight = cur.left;
            if (mostRight != null) {  // 到达最左边节点

                while (mostRight.right != null && mostRight.right != cur) {
                    mostRight = mostRight.right;
                }

                if (mostRight.right == null) {
                    // 开到前驱节点，建立线索指针
                    mostRight.right = cur;
                    cur = cur.left;
                    continue;
                } else {
                    // 删除线索指针
                    mostRight.right = null;
                    printNode(cur.left);
                }
            }
            cur = cur.right;
        }

        // 最右节点，没有后驱节点，需要单独打印链表
        printNode(root);
    }

    private static void printNode(TreeNode head) {

        TreeNode tail = reverse(head);

        while (tail != null) {
            System.out.print(tail.v + " ");
            tail = tail.right;
        }

        reverse(tail);
    }

    private static TreeNode reverse2(TreeNode head) {
        TreeNode cur = head, prev = null, next;
        while (cur != null) {
            next = cur.right;
            cur.right = prev;
            prev = cur;
            cur = next;
        }
        return prev;
    }

    private static TreeNode reverse(TreeNode head) {

        if (head == null || head.right == null) {
            return head;
        }
        TreeNode tail = reverse(head.right);
        head.right.right = head;
        head.right =null;

        return tail;
    }

    private static class TreeNode {
        int v;
        TreeNode left;
        TreeNode right;

        public TreeNode(int v, TreeNode left, TreeNode right) {
            this.v = v;
            this.left = left;
            this.right = right;
        }
    }

}
